\documentclass[10pt]{amsart}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage[all]{xy}

\renewcommand{\familydefault}{\sfdefault}
\setlength\parindent{0cm}

\newtheorem*{defn}{Definition}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Prob}{Prob}

\title{Theorem }
\date{}

\begin{document}
\maketitle

This theorem indicates that there is a fairly high probability that a random $d$-regular graph will have a higher eigenvalue than we hope for. This occurs here when a vertex has too many self-loops, a case of what is called a tangle.

\subsection*{Statement}
Consider the standard model, $\mathcal{G}_{n,d}$, of random $d$-regular graphs on $n$ vertices. Then for sufficiently large $n$ with probability at least $n^{1-m}-\frac{1}{2}n^{2-2m}$ we have that $\lambda_2(G) > 2\sqrt{d-1}$.

\subsection*{Detailed proof}
We're considering the case in which a graph has at least $m$ self-loops, for $m<d/2$. We'll show that for a value of $m$ large enough relatively to $d$ the second largest eigenvalue will be larger than $2\sqrt{d-1}$ for a sufficiently large value of $n$.\\

Throughout this proof, we'll consider the values of $d$ and $m$ fixed while we'll let the value of $n$ grow.\\

Assume that there are at least $m$ self-loops at the vertex $v_k$, this is the event, which we'll denote by $\tau_k$, that $\pi_i(v_k)= v_k$ for $i = 1, \ldots, m$. This event occurs with probability 1/$n^m$ since we simply fix the first value of its first $m$ permutations.\\

Let us denote by $\tau$ the probability that there are at least $m$ self-loops at some vertex in the graph, so we have
\[
\tau = \bigcup_{k=1}^n \tau_k
\]
and hence, using the principle of inclusion and exclusion, we can estimate the probability of $\tau$ as claimed:
\[
\text{Prob}(\tau) \geq \sum_{k=1}^n \text{Prob}(\tau_k) - \sum_{k_1 \neq k_2} \text{Prob}(\tau_{k_1} \cap \tau_{k_2}) \geq n \frac{1}{n^m} - \binom{n}{2}\left( \frac{1}{n^m}\right)^2 \geq n^{1-m} - \frac{1}{2}n^{2-2m}
\]

Let us now show how such a graph will give rise to a large second eigenvalue. To do this, we'll use Rayleigh quotients to estimate the second largest eigenvalue as stated ????? SOMEWHERE.

Let us assume that in a random $d$-regular graph $G$ we have at least $m$ self-loops at a vertex $v_0$. Denote by $\rho(v)$ the distance of a vertex $v$ to the vertex $v_0$ and for any positive integer $r$ consider the function defined on the vertices $f_r$ given by:
\[
f_r(v) = \begin{cases} \left(\frac{1}{2m-1}\right)^{\rho(v)} & \text{if } \rho(v) \leq r\\ \quad 0 & \text{otherwise}\end{cases}
\]
We would like to estimate the Rayleigh quotient of the function $f_r$. For this, we'll consider the function $\alpha$ defined by:
\[
\alpha(m) = (2m-1) + \frac{d-1}{2m-1}
\]
For which we'll make the following two claims:
\begin{itemize}
\item Under the assumption that $2m-1 > \sqrt{d-1}$ we have that $\alpha(m) > 2\sqrt{d-1}$,
\item If we denote by $A$ the adjacency matrix of our random graph $G$ then $(Af_r)(v) \geq \alpha(m)f_r(v)$ for any vertex $v$ such that $\rho(v)<r$.
\end{itemize}
The first claim simply follows from Cauchy-Schwarz. The second claim follows from the following. Let $v$ be a vertex such that $\rho(v) < r$, then we have that:
\[
(Af_r)(v) = \sum_{w \in V_G}A_{v,w}f_r(w) \geq \left(\frac{1}{2m-1}\right)^{\rho(v)-1} \!\!\!\!\!\!\!\!+\,\, (d-1)\left(\frac{1}{2m-1}\right)^{\rho(v)+1} \!\!\!\!\!\!\!\!= \alpha(m)f_r(v)
\]
This estimate comes from the worst case this computation can take when the vertex $v$ has only one vertex closer to the vertex $v_0$ and the remaining $d-1$ vertices are further away from the vertex $v_0$ than the vertex $v$. The specific case when the vertex $v$ is the vertex $v_0$ is dealt in a similar way:
\[
Af_r(v_0) = \sum_{w \in V_G}A_{v_0w}f_r(w) \geq 2m f_r(v_0) + (d-2m) \frac{1}{2m-1} = \alpha(m)f_r(v_0)
\]
Here, the worst case is when the vertex $v_0$ has precisely $m$ self-loops (each contributing twice in the adjacency matrix) and hence $d-2m$ adjacent vertices. Note also that $f_r(v_0) = 1$.

We can now estimate the Rayleigh quotient of the function $f_r$. Let us define by $\rangle f,g \langle_r$ the partial scalar product on vertices at distance at most $r$:
\[
\langle f,g \rangle_r = \sum_{\begin{array}{c} w \in V_G\\ \rho(w) \leq r\end{array}}f(w)g(w)
\]
then we can rewrite our above remarks as follow:
\[
\langle f_r,f_r \rangle = \langle f_r,f_r \rangle_r \quad\text{and}\quad \langle Af_r,f_r \rangle \geq \langle Af_r,f_r \rangle_r \geq \alpha(m) \langle f_r,f_r \rangle_{r-1}
\]
This allows to get the following estimate of the Rayleigh quotient of the function $f$<sub>$r$</sub>:
\[
R_A(f_r) = \frac{\langle Af_r,f_r \rangle}{\langle f_r,f_r \rangle} \geq \alpha(m) \frac{\langle f_r,f_r \rangle_{r-1}}{\langle f_r,f_r \rangle_r}
\]
We know that $\alpha(m)$ is at most $2\sqrt{d-1}$ but the remaining fraction being less than 1, we need to work a little to show that it can be made arbitrarily close to 1 for a suitable value of $r$. First we can estimate the difference in these two terms as follow: notice that there are at most $(d-2m)(d-1)^{t-1}$ vertices at distance $t$ from the vertex $v_0$ hence:
\[
\langle f_r,f_r \rangle_r \leq \langle f_r,f_r \rangle_{r-1} + (d-2m)(d-1)^{r-1}\left(\frac{1}{2m-1}\right)^{2r}
\]
And so
\[
\frac{\langle f_r,f_r \rangle_{r-1}}{\langle f_r,f_r \rangle_r} \geq 1 - \frac{(d-2m)(d-1)^{r-1}}{\langle f_r,f_r \rangle_r (2m-1)^{2r}}
\]
Since $f_r(v_0)=1$ we have that $\langle f_r, f_r \rangle_r \geq 1$ and hence
\[
\frac{(d-2m)(d-1)^{r-1}}{\langle f_r,f_r \rangle_r (2m-1)^{2r}} \leq \frac{d-2m}{d-1}\left(\frac{d-1}{(2m-1)^2}\right)^r
\]
Which converges to zero if we let $r$ tend to infinity since ($d$-1)/(2$m$-1)<sup>2</sup> < 1. This implies that for any fixed value of $m$ we can choose a value $\alpha_0$ such that $2\sqrt{d-1} < \alpha_0 < \alpha(m)$ and then choose a value $r_0$ large enough such that:
\[
\frac{d-2m}{d-1}\left(\frac{d-1}{(2m-1)^2}\right)^{r_0} < 1- \frac{\alpha_0}{\alpha(m)}
\]
Which gives the following lower bound on the Rayleigh quotient of the function $f_r$:
\[
R_A(f_r) \geq \alpha(m) \left( 1 - \frac{d-2m}{d-1}\left(\frac{d-1}{(2m-1)^2}\right)^{r_0} \right) > \alpha_0 > 2\sqrt{d-1}
\]

To complete the proof and use lemma ??? we need to find an orthogonal function with a larger Rayleigh quotient that this.

For simplicity, we'll denote by $f$ the function $f_{r_0}$ that we obtained above.

Consider the following set of vertices
\[
N = \left\{ w \in V_G \,|\, \text{dist}_G(w, \text{supp}(f)) \leq 1 \right\}
\]
which contains the support of the function $f$ and all the vertices adjacent to it. We consider now the function $g=1_{V \backslash N}$, which is the characteristic function of the complement set of the set $n$. By construction, the function $f$ is orthogonal to both $g$ and $Ag$. We now proceed to estimate the Rayleigh quotient of $g$. Since $\langle Ag, g \rangle$ is twice the number of edges in the subgraph induced by the vertices in $V \backslash N$ and since the number of edges in that subgraph is at least $(1/2)d|V| - d|N|$, that is, the number of edges adjacent to a vertex in the set $n$ subtracted from the total number of edges in the graph; we obtain that:
\[
R_A(g) \geq \frac{d|V| - 2d|N|}{|V|-|N|} = d - \textrm{O}\!\left( \frac{1}{n} \right)
\]
Since $|V| = n$ and since we can consider $d$ and $|N|$ to be constants at this point. This implies that for $n$ sufficiently large, we'll have:
\[
d-\textrm{O}\!\left(\frac{1}{n}\right) \geq \alpha(m) \geq \alpha_0
\]
And hence $\min\{ R_A(f), R_A(g) \} = R_A(f) > 2\sqrt{d-1}$ which implies that $\lambda_2(G) > 2\sqrt{d-1}$ and concludes this proof.

\end{document}